package com.smh;

import org.junit.jupiter.api.Test;

import java.util.HashMap;

/**
 * @author shiminghui
 * @date 2025/3/13 15:28
 * @description: TODO
 */
public class _040_动态规划 {

    public static HashMap<Integer, Integer> map = new HashMap<>();

    @Test
    public void test() {
        int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        System.out.println(minCostClimbingStairs(cost));
    }

    /**
     * 爬楼梯, 动态规划,每一阶楼梯的花费
     *
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        return doIt(cost.length, cost);
    }

    public int doIt(int n, int[] cost) {
        if (n < 2) {
            return 0;
        }
        int i = n - 2;
        int j = n - 1;
        Integer costi = map.get(i);
        Integer costj = map.get(j);
        int resi = 0;
        int resj = 0;
        if (costi == null) {
            costi = doIt(i, cost);
            map.put(i, costi);
        }
        resi = cost[i] + costi;

        if (costj == null) {
            costj = doIt(j, cost);
            map.put(j, costj);
        }
        resj = cost[j] + costj;

        return Math.min(resi, resj);
    }
}
